#力扣31 下一个排列
from typing import  List
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        # Step 1: 从后向前找到第一个升序对的位置 i
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        # Step 2: 如果找到 i，则从后向前找到第一个大于 nums[i] 的元素
        if i >= 0:
            j = n - 1
            while j > i and nums[j] <= nums[i]:
                j -= 1
            # 交换 nums[i] 和 nums[j]
            nums[i], nums[j] = nums[j], nums[i]

        # Step 3: 反转 i+1 到末尾的部分
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1